class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr||list2 == nullptr)
        {
            return list1==nullptr?list2:list1;
        }
        ListNode* cur1 = list1;
        ListNode* cur2 = list2;
        if(cur1->val>cur2->val)
        {
            cur1 = list2;
            cur2 = list1;
        }//保证cur1指向的是小的那个链表
        ListNode* newhead = new ListNode(cur1->val);
        cur1 = cur1->next;
        ListNode* cur = newhead;
        while(cur1&&cur2)
        {
            if(cur1->val<cur2->val)
            {
                cur->next = cur1;
                cur = cur->next;
                cur1= cur1->next;
            }
            else
            {
                cur->next = cur2;
                cur = cur->next;
                cur2 = cur2->next;
            }
        }
        if(cur1)
        {
            cur->next = cur1;
        }
        if(cur2)
        {
            cur->next = cur2;
        }
        return newhead;
    }
};